package Lee_code;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Lee_216 {
    static int sum;
    static int nums;
    static List<List<Integer>> Res = new ArrayList<>();
    public static List<List<Integer>> combinationSum3(int k, int n) {
        sum = n;
        nums = k;
        List<Integer> list = new ArrayList<Integer>();
        Traceback(list, 1);
        return Res;
    }

    private static void Traceback(List<Integer> list, int start_index) {

        if(list.size()>nums)
        {
            return;
        }
        if(list.size()==nums)
        {
            int temp_sum=0;
            for(int i: list)
            {
                temp_sum = temp_sum + i;
            }
            if (temp_sum == sum)
            {
                Res.add(new ArrayList<>(list));
                return;
            }
        }

        for(int i=start_index; i<=9; i++)
        {
            list.add(i);
            Traceback(list, i+1);

            list.remove(list.size()-1);
            Traceback(list, i+1);
        }
    }

    public static void main(String[] args) {

        List<List<Integer>> result = new ArrayList<>(combinationSum3(3, 7));

    }
}
